package ren.colorful.jikeshijian;

import java.util.Arrays;

public class Fenzhi {
    private int num = 0;

    public static void main(String[] args) {
        int[] a = {1,5,6,2,3,4};
        Fenzhi f = new Fenzhi();
        int count = f.count(a, 6);
        System.out.println(count);
        System.out.println(Arrays.toString(a));
    }

    public int count(int [] a,int n){
        num = 0;
        mergeSortCount(a,0,n-1);
        return num;
    }

    private void mergeSortCount(int[] a, int p, int r) {
        if(p >= r) return;
        int q = (p + r) / 2;
        mergeSortCount(a,p,q);
        mergeSortCount(a,q +1,r );
        merge(a,p,q,r);
    }

    private void merge(int[] a, int p, int q, int r) {
        int i = p,j = q + 1,k = 0;
        int[] tmp = new int[r - p + 1];
        while(i <= q && j <= r){
            if(a[i] <= a[j]){
                tmp[k++] = a[i++];
            }else{
                num += (q-i+1);     //统计 p - q之间,比a[j]大的元素个数
                tmp[k++] = a[j++];
            }
        }

        while(i <= q){
            tmp[k++] = a[i++];
        }

        while(j <= r){
            tmp[k++] = a[j++];
        }

        for(i = 0; i <= r-p; ++i){ //从tmp拷贝回a
            a[p+i] = tmp[i];
        }
    }
}


























